/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/maximal-square
   @Language: C++
   @Datetime: 19-05-28 17:39
   */

// Method 1, DP, Time O(m*n), Space O(m*n), Time 56ms
class Solution {
public:
	/**
	 * @param matrix: a matrix of 0 and 1
	 * @return: an integer
	 */
	int maxSquare(vector<vector<int> > &matrix) {
		// write your code here
		if(matrix.empty() || matrix[0].empty()) return 0;
		int m=matrix.size(), n=matrix[0].size(), res=0;
		vector<vector<int> > dp(m,vector<int>(n,0));
		for (int i=0; i<m; ++i){
			for (int j=0; j<n; ++j){
				if(i==0 || j==0) dp[i][j]=matrix[i][j];
				else if(matrix[i][j])
					dp[i][j]=1+min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]));
				res=max(res,dp[i][j]);
			}
		}
		return res*res;
	}
};


// Method 2, DP, Time O(m*n), Space O(n), Time 54ms
class Solution {
public:
	/**
	 * @param matrix: a matrix of 0 and 1
	 * @return: an integer
	 */
	int maxSquare(vector<vector<int> > &matrix) {
		// write your code here
		if(matrix.empty() || matrix[0].empty()) return 0;
		int m=matrix.size(), n=matrix[0].size(), res=0;
		vector<int> dp(n,0);
		for (int i=0, pre=0; i<m; ++i) {
			for (int j=0, t=0; j<n; ++j) {
				t=dp[j];
				if(j==0) dp[j]=matrix[i][j];
				else if(matrix[i][j]==0) dp[j]=0;
				else dp[j]=1+min(pre,min(dp[j-1],dp[j]));
				res=max(res,dp[j]);
				pre=t;
			}
		}
		return res*res;
	}
};
